package Top200;

import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-02-23 10:24
 * 按照开始时间排序
 */
public class merge56 {
    public int[][] merge1(int[][] intervals) {
        int n=intervals.length;
        if (n==1) return new int[][]{intervals[0]};
        List<int[]> reslist=new LinkedList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        int i=0;
        //挨个取出区间找到其最大的合并结果，加入到结果中
        while (i<n){
            int start=intervals[i][0];
            int end=intervals[i][1];
            int j=i+1;
            while (j<n){
                if (intervals[j][0]>end) break;
                if (intervals[j][1]>=end){
                    end=intervals[j][1];
                    j++;
                }else {
                 j++;
                }
            }
            reslist.add(new int[]{start,end});
            i=j;
        }
        int[][] res=new int[reslist.size()][2];
        for (int j = 0; j < res.length; j++) {
            res[j]=reslist.get(j);
        }
        return res;
    }

    public int[][] merge(int[][] intervals) {
        int n=intervals.length;
        if (n==1) return new int[][]{intervals[0]};
        LinkedList<int[]> reslist=new LinkedList<>();
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0]-o2[0];
            }
        });
        //直接从list中取出最后的一个区间，判断是否可以合并，可以合并则将最后一个区间变为合并后的区间，否则将当前区间加入到结果的最后一个
        reslist.add(intervals[0]);
        for (int i = 1; i < n; i++) {
            int[] cur=intervals[i];
            int[] last = reslist.getLast();
            if (cur[0]<=last[1]){
                last[1]=Math.max(cur[1],last[1]);
            }else {
                reslist.add(cur);
            }
        }
        int[][] res=new int[reslist.size()][2];
        for (int j = 0; j < res.length; j++) {
            res[j]=reslist.get(j);
        }
        return res;
    }
}
